package code.BinaryTree;

import struct.Tree;
import struct.TreeNode;

public class TreeDepth {
	public static void main(String[] args) {
		TreeNode tree = Tree.constructTree("[3,9,20,null,null,15,7]");
		TreeDepth maxDepth = new TreeDepth();
		int i = maxDepth.maxDepth(tree);
		System.out.println(i);

		boolean balance = maxDepth.isBalanced(tree);
		System.out.println(balance);
	}

	public int maxDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
	}

	//判断二叉树是否为平衡二叉树 110. 平衡二叉树
	public boolean isBalanced(TreeNode root) {
		boolean[] ints = new boolean[1];
		ints[0] = true;
		isBalanceT(root, ints);
		return ints[0];
	}

	public int isBalanceT(TreeNode root, boolean[] result) {
		if (root == null) {
			return 0;
		}
		int lH = isBalanceT(root.left, result) + 1;
		int rH = isBalanceT(root.right, result) + 1;
		if (Math.abs(lH - rH) > 1) {
			result[0] = false;
			return 0;
		}
		return Math.max(lH, rH);
	}

	//111. 二叉树的最小深度
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = minDepth(root.left);
		int right = minDepth(root.right);
		if (left == 0) {
			return right + 1;
		} else if (right == 0) {
			return left + 1;
		}
		return Math.min(left, right) + 1;
	}
}
